Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time
Identifieur interne : 005E56 ( Main/Exploration ); précédent : 005E55; suivant : 005E57Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time
Auteurs : Olivier Bournez ; Felipe Cucker ; Paulin Jacobé De Naurois ; Jean-Yves MarionSource :
- Journal of Logic and Computation ; 2005.
English descriptors
Abstract
We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time over an arbitrary structure can be characterized in terms of safe recursion. We show that polynomial parallel time over an arbitrary structure can be characterized in terms of safe recursion with substitutions.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 004007
- to stream Crin, to step Curation: 004007
- to stream Crin, to step Checkpoint: 000304
- to stream Main, to step Merge: 006079
- to stream Main, to step Curation: 005E56
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="361">Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time</title></titleStmt><publicationStmt><idno type="RBID">CRIN:bournez04g</idno><date when="2005" year="2005">2005</date><idno type="wicri:Area/Crin/Corpus">004007</idno><idno type="wicri:Area/Crin/Curation">004007</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">004007</idno><idno type="wicri:Area/Crin/Checkpoint">000304</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000304</idno><idno type="wicri:Area/Main/Merge">006079</idno><idno type="wicri:Area/Main/Curation">005E56</idno><idno type="wicri:Area/Main/Exploration">005E56</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></author><author><name sortKey="Cucker, Felipe" sort="Cucker, Felipe" uniqKey="Cucker F" first="Felipe" last="Cucker">Felipe Cucker</name></author><author><name sortKey="Jacobe De Naurois, Paulin" sort="Jacobe De Naurois, Paulin" uniqKey="Jacobe De Naurois P" first="Paulin" last="Jacobé De Naurois">Paulin Jacobé De Naurois</name></author><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></author></analytic><series><title level="j">Journal of Logic and Computation</title><imprint><date when="2005" type="published">2005</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>blum shub smale model</term><term>complexity</term><term>implicit complexity</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="1113">We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time over an arbitrary structure can be characterized in terms of safe recursion. We show that polynomial parallel time over an arbitrary structure can be characterized in terms of safe recursion with substitutions.</div></front></TEI><affiliations><list></list><tree><noCountry><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name><name sortKey="Cucker, Felipe" sort="Cucker, Felipe" uniqKey="Cucker F" first="Felipe" last="Cucker">Felipe Cucker</name><name sortKey="Jacobe De Naurois, Paulin" sort="Jacobe De Naurois, Paulin" uniqKey="Jacobe De Naurois P" first="Paulin" last="Jacobé De Naurois">Paulin Jacobé De Naurois</name><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></noCountry></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005E56 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 005E56 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= CRIN:bournez04g
|texte= Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time
}}
| This area was generated with Dilib version V0.6.33. |  |